#include "AllSort.h"
#include "Stack.h"
void InsertSort(int* a, int n)
{
   for(int i=0;i<n-1;i++)
   {
    int end=i;
    int tmp=a[end+1];//后面一个
    while(end>=0)
    {
        if(tmp<a[end])
        {
            a[end+1]=a[end];
            end--;
        }
        else
        {
            break;
        }
    }
    a[end+1]=tmp;//升序 当找到比tmp小的数a[end] 那么tmp排在它后面 tmp和a[end+1]交换
   } 
}

// 希尔排序
void ShellSort(int* a, int n)
{
    int gap=n;
    while(gap>1)
    {
        gap= gap / 3 + 1;//找到区间大小合适的gap值  第一次10/3+1=4 第二次4/3+1=2
        //gap值套入插入排序
        for(int i=0;i<n-gap;i++)
        {
            int end=i;
            int tmp=a[end+gap];
            while(end>=0)
            {
                if(tmp<a[end])
                {
                    a[end+gap]=a[end];
                    end-=gap;
                }
                else
                {
                    break;
                }
            }
            a[end+gap]=tmp;
        }
    }
}


// 选择排序
void SelectSort(int* a, int n)//找最小 再交换
{
    int min=0;
    for(int i=0;i<n-1;i++)
    {
        min=i;
        for(int j=i+1;j<n;j++)
        {
            if(a[min]>a[j])
            min=j;
        }
        Swap(&a[i],&a[min]);
    }
}

// 堆排序
void AdjustDown(int* a, int n, int parent)//调整
{
    int child=parent*2+1;
    while(child<n)
    {
        if(child+1<n&&a[child+1]>a[child]) child++;

        if(a[child]>a[parent])
        {
            Swap(&a[child],&a[parent]);
            parent=child;
            child=parent*2+1;
        }
        else break;
    }
}
void HeapSort(int* a, int n)
{
    //建大堆
    //从最下边的子树向下调整
    for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

    int end=n-1;
    while (end>0)
    {
        Swap(&a[0],&a[end]);//把最大的数和末尾交换 再重新调整 保证以后每个最大的数都在顶点 
        AdjustDown(a,end,0);
        end--;
    }
}

// 冒泡排序
void BubbleSort(int* a, int n)//相邻两个比大小
{
    for(int i=0;i<n;i++)
    {
        for(int j=1;j<n-i;j++)
        {
            if(a[j-1]>a[j])
            {
                Swap(&a[j-1],&a[j]);
            }
        }
    }
}

//三数取中
int GetMidIndex(int *a,int begin,int end)
{
    int mid=(begin+end)/2;
    if(a[begin]>a[mid])
    {
        if(a[mid]>a[end])
        {
            return mid;  //begin> mid >end
        }
        else if (a[begin]>a[end])//begin > mid < end  mid最小 再比较begin和end 
            return end;  //begin> end >mid   
            else         //谁小谁是中间值
            return begin;//end> begin >mid
    }
    else //begin<mid
    {
        if(a[begin]>a[end])
        {
            return begin; //end< begin <mid
        }
        else if(a[mid]>a[end])//mid > begin < end   begin最小 再比较mid和end
            return end;   //mid> end >begin
            else
            return mid;   //begin< mid <end
    }
}

// 快速排序递归实现  升序：右先找小 左再找大
void QuickSort(int* a,int begin,int end)
{
    if(begin>=end)  return;
    if((end-begin+1)<15)//小区间优化 ：当区间<15 直接使用插入排序代替 减少递归次数
    {
        InsertSort(a+begin,end-begin+1);
        //1 2 3 4 5 | 4 6 4 3 1 区间在｜后面  排的是｜后的区间数组 所以a+begin
    }
    else
    {
        //int key=PartSort1(a, begin , end);//封装
        //int key=PartSort2(a, begin , end);//封装
        int key=PartSort3(a, begin , end);//封装

        QuickSort(a,begin,key-1);//key-1是左区间的最大下标
        QuickSort(a,key+1,end);//k+1是右区间最小下标
    }
}
// 快速排序hoare版本
int PartSort1(int* a, int begin, int end)
{
    int mid=GetMidIndex(a,begin,end);//三数取中
    Swap(&a[begin],&a[mid]);//把中间数和第一个交换 让它变成key
    
    int left=begin,right=end;
    int key=left;
    while (left<right)                      //key在左边先走右边
    {
        while (left<right&&a[right]>=a[key])//当不相遇时，右边找小于key的下标
        {
            right--;                        
        }
        while (left<right&&a[left]<=a[key])//不相遇时，左边找大于key的下标
        {
            left++;
        }
        Swap(&a[left],&a[right]);

    }
    
        Swap(&a[left],&a[key]);//key的值和最后left right相遇的值交换 key即归位
        key=left;//左右被key分隔开
        return key;
}


// 快速排序挖坑法
int PartSort2(int* a, int begin, int end)
{
    int mid =GetMidIndex(a,begin,end);
    Swap(&a[begin],&a[mid]);

    int left=begin,right=end;
    int key=a[left];//把第一个坑中的值保存起来
    int hole=left;//坑位
    while(left<right)
    {
        while(left<right&&a[right]<=key)//右找大
        {
            right--;
        }
        a[hole]=a[right];//坑位放值
        hole=right;     //新坑
        while(left<right&&a[left]>=key)//左找小
        {
            left++;
        }
        a[hole]=a[left];
        hole=left;
    }
    a[hole]=key;//把第一个坑中的值放到最后的坑里
    return hole;//返回分割区间的key值
}

// 快速排序前后指针法
int PartSort3(int* a, int begin, int end)
{
    int key=begin;
    int prev=begin,cur=begin+1;
    while(cur<=end)
    {   //双指针法：cur一直往后走 遇到比key小的值 prev往后走1步 然后交换值
        if(a[cur]<a[key] && ++prev!=cur) //后面的条件：交换也有代价(建立栈帧)
        {
            Swap(&a[prev],&a[cur]);
        }
        cur++;
    }
    Swap(&a[prev],&a[key]);
    key=prev;//最后prev所在的位置则是分割区间的位置key
    return key;
}

// 快速排序 非递归实现 
void QuickSortNonR(int* a, int begin, int end)
{
    Stack st;
    StackInit(&st);
    StackPush(&st,begin);//先入后出
    StackPush(&st,end);//后入先出
    while(!StackEmpty(&st))
    {
        int right=StackTop(&st);//取栈顶数据 end
        StackPop(&st);//出栈
        int left=StackTop(&st);//第二个就是 begin
        StackPop(&st);

        int key=PartSort1(a,left,right);//取分割区间的key
        //分割成 left ~ key-1  key  key+1 ~ right
        //先入右边区间 再入左边区间
        if(key+1<right)//如果区间只有一个值 就不用再排了
        {
            StackPush(&st,key+1);//先入右边区间的最左
            StackPush(&st,right);//后入右边区间的最右 和初始化时一样
        }
        if(left<key-1)//如果区间只有一个值 就不用再排了
        {
            StackPush(&st,left);//先入左边区间的最左
            StackPush(&st,key-1);//后入左边区间的最右
        }


    }
    StackDestroy(&st);
}

//













//打印
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}


void Swap(int* a,int*b)
{
    int t=*a;
    *a=*b;
    *b=t;
}